#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    //@ysh's method
    // int largestSumAfterKNegations(vector<int> &nums, int k)
    // {
    //     sort(nums.begin(), nums.end());
    //     int split_point = nums.size();
    //     for (size_t i = 0; i < nums.size(); i++)
    //     {
    //         if (nums[i] >= 0)
    //         {
    //             split_point = i;
    //             break;
    //         }
    //     }
    //     int start_index = 0;
    //     while (k > 0)
    //     {
    //         k--;
    //         if ((split_point != (int)nums.size()) && (start_index == split_point - 1) && (abs(nums[split_point - 1]) < nums[split_point]))
    //         {
    //             nums[start_index] = -nums[start_index];
    //             continue;
    //         }
    //         if (start_index < split_point && start_index < (int)nums.size() - 1)
    //         {
    //             nums[start_index] = -nums[start_index];
    //             start_index++;
    //         }
    //         else
    //         {
    //             nums[start_index] = -nums[start_index];
    //         }
    //     }
    //     int sum = accumulate(nums.begin(), nums.end(), 0);
    //     return sum;
    // }
    
    static bool cmp(int &a, int &b)
    {
        return abs(a) > abs(b);
    }
    //@book's method
    int largestSumAfterKNegations(vector<int> &nums, int k)
    {
        sort(nums.begin(), nums.end(), cmp);
        int length = nums.size();
        for (int i = 0; i < length; i++)
        {
            if (nums[i] < 0 && k > 0)
            {
                nums[i] *= -1;
                k--;
            }
        }
        if (k % 2 == 1)
        {
            nums[length - 1] *= -1;
        }
        int sum = accumulate(nums.begin(), nums.end(), 0);
        return sum;
    }
};

int main()
{
    vector<int> nums{-8, 3, -5, -3, -5, -2};
    Solution sol;
    cout << sol.largestSumAfterKNegations(nums, 6) << endl;
    return 0;
}